﻿#define _CRT_SECURE_NO_WARNINGS 1
阶乘分解
给定整数 N，试把阶乘 N!分解质因数，按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可。

输入格式
一个整数 N。

输出格式
N!分解质因数后的结果，共若干行，每行一对 pi, ci，表示含有 pcii 项。按照 pi 从小到大的顺序输出。

数据范围
3≤N≤106
输入样例：
5
输出样例：
2 3
3 1
5 1
样例解释
5 != 120 = 23∗3∗5
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN = 1e6;
int primes[MAXN], primeCnt = 0;
bool notPrime[2 * MAXN];
void initPrime(int x) {
    for (int i = 2; i <= x; i++) {
        if (notPrime[i])continue;
        for (int j = 2; j <= x / i; j++) {
            notPrime[i * j] = 1;
        }
    }
    for (int i = 2; i <= x; i++)
        if (!notPrime[i])primes[++primeCnt] = i;
}
int ans[MAXN], ansValue[MAXN];
int main() {
    int n;
    scanf("%d", &n);
    initPrime(n);
    for (int i = 1; i <= primeCnt; i++) {
        int tmpN = n, nowPrime = primes[i], nowAns = 0;
        while (tmpN) {
            nowAns += (tmpN / nowPrime);
            tmpN /= nowPrime;
        }
        printf("%d %d\n", nowPrime, nowAns);
    }
    return 0;
}